The present invention relates to method for implementing a single chip shared channel decoder supporting a multiplicity of variable bit rate carriers. More particularly, the present invention relates to a method for decoding an input signal comprising a plurality of channel symbols utilizing Viterbi decoding for use in onboard processing satellites in which trade-offs are made between memory for storing the survivor paths and bit error rate performance.
Among several conventional algorithms for decoding convolutional codes, the Viterbi algorithm achieves maximum likelihood decoding and has been extensively utilized to improve the reliability of digital communication links. For each received channel symbol in an encoded input signal, the Viterbi algorithm initially computes a set of branch metrics. The branch metrics are then used by add/compare/select (ACS) units for computing and updating path metrics. For each state, in addition to the new path metrics, a sequence of decisions are made for the survivor paths and stored. When memory space is readily available and delay is not of any concern, the decoder can continue processing received data and output estimates for information bits at the end of message. In practice, however, messages are truncated and after a delay of T decoding steps, the decoder outputs estimates for information bits in a continuous mode.
There are two approaches to implement the truncated Viterbi algorithm. In a first approach, known as survivor exchange, the path metrics, as well as the survivor paths, are updated by the ACS operation and routed among the neighboring trellis states. As shown in FIG. 1, the subsystems of the truncated Viterbi algorithm decoder using the survivor exchange method comprise a branch metric calculator 11 for computing branch metrics Bt, a plurality of add-compare-select (ACS) units 12 for computing path metrics xcex93t and survivor paths Et, a memory 13 for storing new path metrics xcex93t and the survivor paths Et, and a memory 14 for storing path metrics xcex93txe2x88x921 and survived paths Etxe2x88x921, of prior trellis/decoding step txe2x88x921. For a code of rate xc2xd or its punctured versions, the truncation length T is about 60 to 120 bits. While this approach may provide savings in the required memory for storing survivor paths it entails a large interprocessor communication bandwidth and a large percentage of the chip area must be allocated to wiring.
In a second approach known as a traceback method, the sequence of survived paths are stored in a traceback RAM which is placed outside of the ACS units. As shown in FIG. 2, the subsystems of the truncated Viterbi algorithm decoder using the traceback method comprise a branch metric calculator 11 for computing branch metrics Bt, a plurality of ACS units 12, and a memory 23 for storing new path metrics xcex93t, a memory 24 for storing old path metrics xcex93txe2x88x921. Communications between each of the ACS units 12 and a traceback module (not shown) can be as small as one bit per decoder state per decoding step. Number of cells in the traceback RAM is a linear function of the product of number of decoder states S which equals 2m, where m is the memory order of the code, and the truncation length T.
Studies on the feasibility of VLSI implementation of a shared channel decoder (SCD) using the Viterbi algorithm have indicated that the maximum number of carriers processed by a single chip decoder is limited by the chip space allocated for storing the survived paths. This conclusion is valid for both the traceback method and the survivor exchange method for implementing a Viterbi algorithm decoder. The importance of RAM for storing surviving paths is emphasized by noting that it occupies about 50 percent of the chip area of a single channel decoder.
A decoding method and apparatus is presented which provides a high degree of flexibility allowing tradeoffs among such important system parameters as processing speed, required on-chip RAM, bit error rate (BER) performance, and throughput. The decoding method of the present invention uses the Viterbi algorithm for selecting survivor paths terminating on each trellis state. This decoding method is then applied for realization of a SCD. Several variations of the decoding method are examined for minimizing the required chip space of an Application Specific Integrated Circuit (ASIC) and optimizing the maximum number of channels. In a maximum likelihood shared channel decoding procedure, the ACS units must operate at 16xc3x9764 Kbps, or 1 Mbps for decoding a group of sixteen 64 Kbps channels. However, with the current CMOS technology, the same ACS units, occupying roughly the same amount of chip area, can operate more than 60 MHz. The decoding of the present invention method takes advantage of the high speed capability of processing elements for reducing the amount of memory required to store the survived paths.
For the special frequency plan and configuration of shared demodulators, considered for the onboard processing satellites, it is assumed that each channel is either a 64 Kbps carrier, or a 2 Mbps carrier, encoded by a convolutional code of rate xc2xd or its punctured version. In the midband section, it is assumed that frequency is planned so that each demodulator either demodulates only one 2 Mbps carrier or up to sixteen 64 Kbps carriers. The BER performance of the proposed decoding algorithm is evaluated by computer simulations. Feasibility of a single chips SCD for simultaneously decoding up to sixteen 64 Kbps channels is examined for the midband. For the sidebands, a SCD using MLD is proposed since there are at most six 2 Mbps carriers in these bands.
The required chip space can be minimized by selecting an architecture which is based on parallel processing of states and bit serial communications among the neighboring states. While the decoding method of the present invention is intended for an onboard processing satellite, it can certainly be also used in satellite or terrestrial earth stations receiving several low bit rate channels.
These and other features, aspects and advantages of the present invention will become better understood with reference to the following detailed description, appended claims, and accompanying drawings, wherein:
FIG. 1 is a block diagram of a truncated Viterbi Algorithm decoder using the survivor exchange method;
FIG. 2 is a block diagram of a truncated Viterbi Algorithm decoder using a traceback module;
FIG. 3 is a block diagram of a truncated Viterbi Algorithm decoder according to a first embodiment of the present invention;
FIG. 4 is a flowchart of the method of implementing a truncated Viterbi Algorithm decoder according to a first embodiment of the present invention;
FIG. 5 is a block diagram of a truncated Viterbi Algorithm decoder according to a second embodiment of the present invention;
FIG. 6 is a flowchart of the method of implementing a truncated Viterbi Algorithm decoder according to a second embodiment of the present invention;
FIG. 7 is a graph illustrating the number of gates vs. truncation length for the decoding method of the first embodiment of the present invention;
FIG. 8 is a graph illustrating the number of gates vs. truncation length for the decoding method of the second embodiment of the present invention;
FIGS. 9-13 are graphs illustrating BER performance for different truncation lengths for the decoding method of the first embodiment of the present invention;
FIGS. 14-18 are graphs illustrating BER performance for different truncation lengths for the decoding method of the second embodiment of the present invention;
FIG. 19 illustrates a configuration for memory for storing branch metrics;
FIG. 20 illustrates a configuration of ACS units.